/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package matematikapirma.sys;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import matematikapirma.Bounds;
import matematikapirma.Curve;
import matematikapirma.Point;

/**
 *
 * @author Tadas
 */
public class IntersectionEngine {

    public IntersectionEngine() {
    }

    public class BoundsCarrier {

        private Bounds bounds;
        private int start;
        private int end;

        public BoundsCarrier(Bounds bounds, int start, int end) {
            this.start = start;
            this.end = end;
            this.bounds = bounds;
        }

        /**
         * @return the bounds
         */
        public Bounds getBounds() {
            return bounds;
        }

        /**
         * @return the start
         */
        public int getStart() {
            return start;
        }

        /**
         * @return the end
         */
        public int getEnd() {
            return end;
        }
    }

    public List<Point> getIntersectionPoints(Curve one, Curve two) {
        List<Point> points = new ArrayList<Point>();
        if (one == two) {
            throw new RuntimeException("Check agains self");
        }

        if (one.getPoints().size() < 2 || two.getPoints().size() < 2) {
            return points;
        }
        if (one.getBounds().intersects(two.getBounds())) {
            intersects(points, one, two, 0, one.getPoints().size() - 1, 0, two.getPoints().size() - 1);
        }
        return points;
    }

    protected void intersects(List<Point> returnPoints, Curve one, Curve two, int startOne, int endOne, int startTwo, int endTwo) {

        if (Math.abs(startOne - endOne) == 1 && Math.abs(startTwo - endTwo) == 1) {
            Point a1 = one.getPoints().get(startOne);
            Point a2 = one.getPoints().get(endOne);
            Point b1 = two.getPoints().get(startTwo);
            Point b2 = two.getPoints().get(endTwo);


            Point point = getIntersectionFromPoints(a1, a2, b1, b2);
            if ((((a1.getX() >= point.getX() && a2.getX() <= point.getX()) || (a1.getX() <= point.getX() && a2.getX() >= point.getX()))
                    && ((a1.getY() >= point.getY() && a2.getY() <= point.getY()) || (a1.getY() <= point.getY() && a2.getY() >= point.getY())))
                    && (((b1.getX() >= point.getX() && b2.getX() <= point.getX()) || (b1.getX() <= point.getX() && b2.getX() >= point.getX()))
                    && ((b1.getY() >= point.getY() && b2.getY() <= point.getY()) || (b1.getY() <= point.getY() && b2.getY() >= point.getY())))) {

                //System.out.println("Given points: a1: " + a1 + " a2: " + a2 + " b1: " + b1 + " b2: " + b2);
                //System.out.println("New point - x: " + point.getX() + " y: " + point.getY());
                returnPoints.add(point);
            }
            return;
        }

        int partStartOne = startOne + (endOne - startOne) / 2;
        int partStartTwo = startTwo + (endTwo - startTwo) / 2;

        if (endOne == 0 || endTwo == 0) {
            throw new RuntimeException("End should be >0");
        }


        List<BoundsCarrier> oneBounds = new LinkedList<BoundsCarrier>();
        List<BoundsCarrier> twoBounds = new LinkedList<BoundsCarrier>();

        if (startOne != partStartOne) {
            Bounds firstOnePart = getBoundsFromPointPart(one.getPoints(), startOne, partStartOne);
            oneBounds.add(new BoundsCarrier(firstOnePart, startOne, partStartOne));
            Bounds secondOnePart = getBoundsFromPointPart(one.getPoints(), partStartOne, endOne);
            oneBounds.add(new BoundsCarrier(secondOnePart, partStartOne, endOne));
        } else {
            Bounds onePartSingle = getBoundsFromPointPart(one.getPoints(), startOne, endOne);
            oneBounds.add(new BoundsCarrier(onePartSingle, startOne, endOne));
        }

        if (startTwo != partStartTwo) {
            Bounds firstTwoPart = getBoundsFromPointPart(two.getPoints(), startTwo, partStartTwo);
            twoBounds.add(new BoundsCarrier(firstTwoPart, startTwo, partStartTwo));
            Bounds secondTwoPart = getBoundsFromPointPart(two.getPoints(), partStartTwo, endTwo);
            twoBounds.add(new BoundsCarrier(secondTwoPart, partStartTwo, endTwo));

        } else {
            Bounds twoPartSingle = getBoundsFromPointPart(two.getPoints(), startTwo, endTwo);
            twoBounds.add(new BoundsCarrier(twoPartSingle, startTwo, endTwo));
        }


        for (BoundsCarrier firstBound : oneBounds) {
            for (BoundsCarrier secondBound : twoBounds) {
                if (firstBound.getBounds().intersects(secondBound.getBounds())) {



                    intersects(returnPoints, one, two, firstBound.getStart(), firstBound.getEnd(), secondBound.getStart(), secondBound.getEnd());
                } else {
                }
            }
        }


    }

    protected Point getIntersectionFromPoints(Point a1, Point a2, Point b1, Point b2) {
        double diffY = (a2.getX() - a1.getX());
        if (diffY == 0) {
            diffY = 1e-10;
        }
        double ka = (a2.getY() - a1.getY()) / diffY;// paimti tangenta

        double diffX = (b2.getX() - b1.getX());
        if (diffX == 0) {
            diffX = 1e-10;
        }
        double kb = (b2.getY() - b1.getY()) / diffX;

        if (kb == 0.0) {
            kb = 1e-10;
        }

        if (ka == 0.0) {
            ka = 1e-10;
        }

        double ba = a1.getY() - ka * a1.getX();
        double bb = b1.getY() - kb * b1.getX();

        double x = (bb - ba) / (ka - kb);
        double y = (ba / ka - bb / kb) / (1.0 / ka - 1.0 / kb);


        return new MPoint(x, y);

    }

    protected Bounds getBoundsFromPointPart(List<Point> points, int start, int end) {
        double minx, maxx, miny, maxy;
        minx = maxx = miny = maxy = 0.0;
        minx = miny = 1e10;
        for (int i = start; i <= end; i++) {
            Point point = points.get(i);
            if (maxx < point.getX()) {
                maxx = point.getX();
            }
            if (minx > point.getX()) {
                minx = point.getX();
            }
            if (maxy < point.getY()) {
                maxy = point.getY();
            }
            if (miny > point.getY()) {
                miny = point.getY();
            }
        }
        return new SimpleBounds(minx, miny, maxx, maxy);
    }
}
